It is possible for a customer facility connected to a multistage switching network to occasionally be blocked from being connected as desired because the network happens to be interconnected in a manner that prevents effecting the desired interconnection. This, of course, is an undesirable situation which, in an appropriately designed network, is remedied by dismantling one or more existing interconnections and rearranging the interconnection paths to accommodate the new request. When such a rearrangement is possible, it is said that the new assignment, which is the new set of interconnections desired to be established, is realizable. A switching network which can realize all possible assignments without rearranging existing connections is said to be non-blocking, while a network which can realize all possible assignments only by occasionally rearranging existing connections is said to be rearrangeable. Typical rearrangeable networks have many fewer crosspoints than their non-blocking counterparts. An illustrative rearrangeable network, along with the common control equipment associated therewith, is disclosed in U.S. Pat. No. 3,129,407 issued to M. C. Paull on Apr. 14, 1964. Other rearrangeable networks are disclosed in the article by V. E. Benes, "On Rearrangeable Three-Stage Connecting Networks," Bell System Technical Journal, Vol. 41, No. 5, September 1962, pages 1481-1492 and in U.S. Pat. No. 4,038,638 issued to F. K. Hwang on July 26, 1977. Each of these known switching networks is, however, a rearrangeable point-to-point network rather than a rearrangeable multiconnection network. Further each of these networks comprises three or more stages of switching. In applications where network distortion and delay parameters directly related to the number of crosspoints required to effect a given connection are important, the transmission quality obtainable through such three-stage networks is therefore limited.
U.S. Pat. No. 4,556,007 issued to G. W. Richards on Jan. 21, 1986, discloses a two-stage, multiconnection switching network including an innovative connection arrangement that permanently connects each network input channel to a multiplicity of first stage switch inlets in a predetermined pattern. For any given assignment of input channels to the network output channels connected to a second stage switch, the network can always be arranged such that each input channel is connected by a different first stage switch to the second stage switch and therefore to the output channels which are assigned that input channel. Accordingly, the switching network is a rearrangeable multiconnection network that avoids blocking. The innovative connection pattern advantageously eliminates the need for additional stages of switching thereby reducing both the total number of network crosspoints and the number of crosspoints used to effect each interconnection.
The above-mentioned Richards patent discloses a single explicit design method for designing the connection arrangement. Although the method is effective in constructing rearrangeable, two-stage networks, the absence of other, more general design methods limits the freedom of network designers in optimizing their designs in view of practical network construction parameters such as the maximum number of terminals per circuit pack and the power dissipated per circuit pack, limits on the size of failure groups and the number of first stage switches each input channel is connected to, and constraints on the number of network input and output channels (e.g., restricting to powers of two).
In view of the foregoing, a recognized problem in the art is the limited class of known rearrangeable, two-stage networks.